# 质数计数：https://leetcode-cn.com/problems/count-primes/submissions/

# 最简单的暴力破解，可惜会超时，时间复杂度是O(n^2)
class Solution:
    def countPrimes(self, n: int) -> int:
        """
            暴力解法，一个一个尝试
        """
        if n == 0 or n == 1: return 0

        count = 0
        for num in range(2, n+1):
            for i in range(2, num):
                if num % i == 0: break
            else:
                count += 1
        return count 


# 埃氏筛2088 ms, 勉强通过~~  但是算法时间复杂度是减少不少为：O(nlog(logn))
class Solution:
    def countPrimes(self, n: int) -> int:
        """
            埃氏筛： 如果一个是x是质数，那么2x，3x，4x....一定不是质数，可以忽略掉。
            也就是说，遍历到一个质数，就去去掉他能找到的所有非质数，效率会高很多。
        """
        if n == 0 or n == 1: return 0

        count = 0
        # 定义一个数组，标记哪些是质数，空间换取时间
        notPrimes = [False for i in range(n)]
        # num 既是这个数字，也是对应的下标
        for num in range(2, n):
            # 如果这个位置上不是质数，那就跳过
            if notPrimes[num]: continue
            # 否则标记后面所有的非质数（与当前质数相关的）
            for i in range(num, n, num):
                notPrimes[i] = True
            count += 1    

        return count 